package days48;

import java.util.*;

public class day45 {
    public int maxProduct(String[] words) {

        int[] status = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            //用位来表示有没有字符，结果都放在state里面
            int state=0;
            for (int j = 0; j < words[i].length(); j++) {
                state |= 1<<(words[i].charAt(j)-'a');
            }
            status[i] =state;
        }
        int max = 0;
        for (int i = 0; i < status.length; i++) {
            for (int j = i+1; j < status.length; j++) {
                if((status[i]&status[j])==0){
                    max = Math.max(max,words[i].length()*words[j].length());
                }
            }
        }
        return max;
    }
    public static int[] twoSum(int[] numbers, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        int[] arr =new int[2];
        for (int i = 0; i < numbers.length; i++) {
            if(map.containsValue(numbers[i])){
                arr[1]= i;
            }else {
                map.put(numbers[i],target-numbers[i]);
            }
        }
        for (int i = 0; i < numbers.length; i++) {
            if(numbers[i]==target-numbers[arr[1]]){
                arr[0] = i;
            }
        }
        return arr;
    }
//    输入：nums = [-1,0,1,2,-1,-4]
//    输出：[[-1,-1,2],[-1,0,1]]
//    [-4,-1,-1,0,1,2]
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list= new ArrayList<>();
        for (int i = 0; i < nums.length-2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l=i+1;
            int r=nums.length-1;
            while (l<r){
                if(nums[l]+nums[r] == -nums[i]){
                    list.add(Arrays.asList(nums[r],nums[l],nums[i]));
                    l++;
                    r--;
                    while (l<r &&nums[l]==nums[l+1]){
                        l++;
                    }
                    while (l<r &&nums[r]==nums[r-1]){
                        r--;
                    }
                }else if (nums[l]+nums[r]>-nums[i]){
                    r--;
                }else {
                    l++;
                }
            }
        }
        return list;
    }


    public static int MoreThanHalfNum_Solution(int [] array) {
        int count =1;
        int a=array[0];
        for (int i = 1; i < array.length; i++) {
            if(a == array[i]){
                count++;
            }else {
                if(count==0){
                    a = array[i];
                    count++;
                }
                count--;
            }
        }
        return a;
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int count = 1;
        int min = Integer.MAX_VALUE;
        int sum = nums[0];
        for (int i = 0,j=1; j < nums.length;) {
            if(j-i== nums.length&&sum<target){
                return 0;
            }
            while (j<nums.length&&sum < target){
                sum+=nums[j];
                count++;
                j++;
            }
            if(count== nums.length&&sum<target){
                return 0;
            }
            min = Math.min(min,count);
            while (i<j && sum>=target){
                sum-=nums[i];
                i++;
                count--;
                if(sum>=target){
                    min = Math.min(min,count);
                }
            }
        }
        return min;
    }
    public static void main(String[] args) {
//        System.out.println(MoreThanHalfNum_Solution(new int[]{2,2,2,2,2,1,3,4,5}));
        System.out.println(minSubArrayLen(11, new int[]{
                1,1,1,1,1,1,1,1}));
    }
}
